# Arithmetic functions
#
# Copyright (C) 2010 Yotam Medini <yotam.medini@gmail.com>
#
# This file is part of Gupicasa.
#
# Gupicasa is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Gupicasa is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Gupicasa.  If not, see <http://www.gnu.org/licenses/>.


def gcd(m, n):
    while n != 0:
        r = m % n
        m = n
        n = r
    return m


def factorize(n):
    np = []
    prime = 2
    while n > 1:
        power = 0
        while n % prime == 0:
            power += 1
            n /= prime
        if power > 0:
            np.append((prime, power))
        prime += 1
    return np


def _powers_next(powers, max_powers):
    pi = 0
    while pi < len(powers) and powers[pi] == max_powers[pi]:
        pi += 1
    has = False
    if pi < len(powers):
        has = True
        powers[pi] += 1
        while pi > 0:
            pi -= 1
            powers[pi] = 0
    return has



def divisors(n):
    factors = factorize(n)
    max_powers = map(lambda np: np[1], factors)
    d = 1
    ds = [d]
    powers = len(factors) * [0]
    while _powers_next(powers, max_powers):
        d = 1
        for pi in range(len(powers)):
            d *= factors[pi][0] ** powers[pi]
        ds.append(d)
    return ds


def isqrt(n):
    r = 0
    r1 = n + 1
    while r < r1 - 1:
        m = (r + r1)/2
        m1 = n / m
        r = min(m, m1)
        r1 = m + m1 - r
    return r
